import java.net.Inet4Address;
import java.util.*;

class RandomizedSet {
    Map<Integer,Integer> map;
    List<Integer> list;
    Random random=new Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list=new LinkedList<>();
        map=new HashMap<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        map.put(val,list.size());
        list.add(list.size(),val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        int tmp=list.get(list.size()-1);
        int index=map.get(val);
        list.set(index,tmp);
        map.put(tmp,index);
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}














class RandomizedSet1 {
    Map<Integer,Integer> map;
    List<Integer> list;
    Random random=new Random();
    public RandomizedSet1() {
        list=new LinkedList<>();
        map=new HashMap<>();
    }

    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        map.put(val,list.size());
        list.add(list.size(),val);
        return true;
    }

    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        int tmp=list.get(list.size()-1);
        int index=map.get(val);
        list.set(index,tmp);
        map.put(tmp,index);
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}









public class project {
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int sum=0;
        int max=0;
        map.put(0,-1);
        for(int i=0;i< nums.length;i++){
            int num=nums[i];
            if(num==1){
                sum++;
            }else{
                sum--;
            }
            if(map.containsKey(sum)){
                max=Math.max(max,i-map.get(sum));
            }else{
                map.put(sum,i);
            }
        }
        return max;
    }







    public int subarraySum(int[] nums, int k) {
        int count=0;
        int sum=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }









    public int subarraySum1(int[] nums, int k) {
        int count=0;
        Map<Integer,Integer> map=new HashMap<>();
        int tmp=0;
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            tmp+=nums[i];
            if(map.containsKey(tmp-k)){
                count+=map.get(tmp-k);
            }
            map.put(tmp,map.getOrDefault(tmp,0)+1);
        }
        return count;
    }












    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k<2){
            return 0;
        }
        int sum=1;
        int right=0;
        int left=0;
        int count=0;
        for(right=0;right<nums.length;right++){
            sum*=nums[right];
            while(sum>=k){
                sum/=nums[left];
                left++;
            }
            count+=right-left+1;
        }
        return count;
    }







    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        if(k<2){
            return 0;
        }
        int sum=1;
        int right=0;
        int left=0;
        int count=0;
        for(right=0;right<nums.length;right++){
            sum*=nums[right];
            while(sum>=k){
                sum/=nums[left];
                left++;
            }
            count+=right-left+1;
        }
        return count;
    }














    public int minSubArrayLen(int target, int[] nums) {
        int i=0;
        int j=0;
        int sum=0;
        int min=Integer.MAX_VALUE;
        while(j<nums.length){
            sum+=nums[j];
            while(sum>=target){
                min=Math.min(j-i+1,min);
                sum-=nums[i];
                i++;
            }
            j++;
        }
        return min==Integer.MAX_VALUE?0:min;
    }











    public int minSubArrayLen1(int target, int[] nums) {
        int min=Integer.MAX_VALUE;
        int i=0;
        int j=0;
        int sum=0;
        while(j<nums.length){
            sum+=nums[j];
            while(sum>=target){
                min=Math.min(j-i+1,min);
                sum-=nums[i];
                i++;
            }
            j++;
        }
        return min==Integer.MAX_VALUE?0:min;
    }












    public int singleNumber(int[] nums) {
        int sum=0;
        int tmp=0;
        for(int i=0;i<32;i++){
            tmp=0;
            for(int n : nums){
                tmp+=((n>>i)&1);
            }
            if(tmp%3!=0){
                sum|=(1<<i);
            }
        }
        return sum;
    }









    public int countDigitOne(int n) {
        int count=0;
        int tmp=0;
        for(int i=1;i<n;i++){
            tmp=i;
            while(tmp>9){
                tmp/=10;
                if(tmp%10==1){
                    count++;
                }
            }
            if(tmp==1){
                count++;
            }
        }
        return count;
    }
}
